package sorting

import "gitee.com/guuzaa/sorting/constraints"

func ShellSort[T constraints.Ordered](arr []T) []T {
	gap := len(arr) / 2
	for gap > 0 {
		for start := 0; start < gap; start++ {
			shellSort(arr, start, gap)
		}
		gap /= 2
	}
	return arr
}

func shellSort[T constraints.Ordered](arr []T, start, gap int) {
	for i := start + gap; i < len(arr); i += gap {
		pos := i
		cur := arr[pos]

		for pos >= gap && cur < arr[pos-gap] {
			arr[pos] = arr[pos-gap]
			pos -= gap
		}

		arr[pos] = cur
	}
}
